package  main.java.leetcode.editor.cn;
//2023-07-02 20:55:32
//编写一个函数，检查输入的链表是否是回文的。 
//
// 
//
// 示例 1： 
//
// 输入： 1->2
//输出： false 
// 
//
// 示例 2： 
//
// 输入： 1->2->2->1
//输出： true 
// 
//
// 
//
// 进阶： 
//你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？ 
// Related Topics 栈 递归 链表 双指针 👍 133 👎 0

import java.util.ArrayList;
import java.util.List;

class PalindromeLinkedListLcci {
    public static void main(String[] args) {
        //创建该题目的对象方便调用
        Solution solution = new PalindromeLinkedListLcci().new Solution();
        ListNode head = new ListNode(-129);
        head.next = new ListNode(-129);
        solution.isPalindrome(head);
    }
    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }
    //leetcode submit region begin(Prohibit modification and deletion)
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isPalindrome(ListNode head) {

        ListNode cur = head;
        List<Integer> arr = new ArrayList<>();
        while (cur != null){
            arr.add(cur.val);
            cur = cur.next;
        }

        int right = arr.size()-1;
        int left = 0;
        while (left<right){
            if(arr.get(left).intValue() != arr.get(right).intValue()){
                return false;
            }
            left++;
            right--;
        }

        return true;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
